Network devices that reside in private networks may communicate with one another along data paths in a network. For example, a network device that resides in one private network may engage in Voice over Internet Protocol (VoIP) communications with a network device that resides in another private network. Often times, the network devices in a private network may have address information that is inaccessible by devices residing outside of the private network. As a result, communications between devices in different private networks may be lost or misrouted. To avoid these communication problems, the network devices in a private network may utilize a Session Traversal Utilities for Network Address Translators (STUN) protocol (e.g., as described by the Internet Engineering Task Force (IETF) Request For Comments (RFC) 5389) to obtain public address information that is accessible by devices outside of the private network. Additionally, to check connectivity between network devices, STUN messages may be sent (e.g., in accordance with an Interactive Connectivity Establishment (ICE) protocol, as described by the IETF RFC 5245) along a network path between network devices before they engage in, for example, VoIP communications. Often times, these connectivity messages traverse or travel across the same network path that is used for VoIP and other rich media communications between the network devices.